package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-28 13:11
 **/
public class LeetCode208 {
    private Node root;

    public LeetCode208() {
        root = new Node(null);
    }

    public void insert(String word) {
        int n = word.length();

        Node temp = root;
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            Node node = temp.children.get(c);
            if (node == null) {
                node = new Node(c);
                temp.children.put(c, node);
            }
            temp = node;
        }
        temp.isEnd = true;
    }

    public boolean search(String word) {
        int n = word.length();
        Node temp = root;
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            Node node = temp.children.get(c);
            if (node == null) {
                return false;
            }

            temp = node;
        }

        if (temp.isEnd) {
            return true;
        }

        return false;
    }

    public boolean startsWith(String prefix) {
        int n = prefix.length();
        Node temp = root;
        for (int i = 0; i < n; i++) {
            char c = prefix.charAt(i);
            Node node = temp.children.get(c);
            if (node == null) {
                return false;
            }

            temp = node;
        }

        return true;
    }

    class Node {
        Character c;
        Map<Character, Node> children;
        boolean isEnd;
        public Node(Character c) {
            this.c = c;
            children = new HashMap<>();
        }
    }

    public static void main(String[] args) {
        LeetCode208 code = new LeetCode208();
        code.insert("apple");
        code.search("apple");

    }
}
